//构造trie树节点
class ACNode{
    constructor(data){
        this.data = data
        this.isEndingChar = false
        this.children = new Map()
        this.length = 0
        this.fail = null
    }
}

class ACTree{
    constructor(){
        this.root = new ACNode("/")
    }

    //构建树
    insert(text){ //将字符分割成每个
        let node = this.root
        for(let char of text){
            if(!node.children.get(char)){
                node.children.set(char,new ACNode(char))
            }
            node = node.children.get(char)
        }

        node.isEndingChar = true
        node.length = text.length
    }

    //构建失败指针
    failurePointer(){
        let root = this.root
        let queue = [] //循环存储器
        queue.push(root)
        while(queue.length>0){
            let currentNode = queue.shift() //每次取存储器中的第一个对象
            for(let child of currentNode.children.values()){
                if(!child){
                    continue
                }

                if(currentNode == root){ //为根节点 其子集的失败指针指向 根节点
                    child.fail = currentNode
                }else{
                    //第二代节点的指向
                    let grandFatherNode = currentNode.fail
                    while(grandFatherNode){
                        let failNode = grandFatherNode.children.get(child.data)
                        if(failNode){
                            child.fail = failNode
                            break
                        }
                        grandFatherNode = grandFatherNode.fail
                    }
                    if(!grandFatherNode){
                        child.fail = root
                    }
                }
                queue.push(child)
            }
           
        }

    }

     //匹配函数
     math(text){
        let root = this.root
        let len = text.length
        let currentNode //记录当前节点
        const data = [] //存储器
        for(let i=0;i<len;i++){
            let char = text[i] 
            if(!currentNode){
                currentNode = root
            }
            //当匹配不到对应，换线
            while(!currentNode.children.get(char) && currentNode != root){
                currentNode = currentNode.fail
            }
            //当匹配到
            currentNode = currentNode.children.get(char)
            
            if(!currentNode){
                currentNode  = this.root
            }
            let tmp = currentNode
            
            while(tmp !=root){
                if(tmp.isEndingChar){
                    console.log(`from ${i - tmp.length + 1} length: ${tmp.length} str: `)
                    data.push(`${text.substr(i - tmp.length + 1,tmp.length)}`)
                }

                 //匹配到了就继续看看其他线有没有可以匹配成功的
                 tmp = tmp.fail 
            }
        }  
        
        return data
    }

}


export function AC_automatic(text,patterns) {
        const autoMeta = new ACTree()
        for(let pattern of patterns){
            autoMeta.insert(pattern)
        }

        autoMeta.failurePointer()

        let data =  autoMeta.math(text)

        return data
}
